package leetcode_动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 出租车的最大盈利 <p>
 * 算法：动态规划
 *
 * @author yezh
 * @date 2023/8/31 18:51
 */
public class _2008 {

    public long maxTaxiEarnings(int n, int[][] rides) {
        // dp[i]: 1 ~ i 可以获得的最大盈利
        // 第 i 个的结果依赖前 i - 1, 所以需要分组
        long[] dp = new long[n + 1];
        List<int[]>[] groups = new ArrayList[n];
        Arrays.setAll(groups, e -> new ArrayList<>());
        for (int[] ride : rides) groups[ride[1] - 1].add(ride);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            for (int[] ride : groups[i - 1])
                dp[i] = Math.max(dp[i], dp[ride[0]] + ride[1] - ride[0] + ride[2]);
        }
        return dp[n];
    }

}
